|
In computing, a threaded binary tree is a binary tree variant that allows fast traversal: given a pointer to a node in a threaded tree, it is possible to cheaply find its in-order successor (and/or predecessor). ==Motivation== Binary trees, including (but not limited to) binary search trees and their variants, can be used to store a set of items in a particular order. For example, a binary search tree assumes data items are somehow ordered and maintain this ordering as part of their insertion and deletion algorithms. One useful operation on such a tree is ''traversal'': visiting the items in the order in which they are stored (which matches the underlying ordering in the case of BST). A simple recursive traversal algorithm that visits each node of a BST is the following. Assume is a pointer to a node, or . "Visiting" can mean performing any action on the node or its contents. Algorithm traverse(): * Input: a pointer to a node (or ) * If , return. * Else: * * traverse(left-child()) * * Visit * * traverse(right-child()) The problem with this algorithm is that, because of its recursion, it uses stack space proportional to the height of a tree. If the tree is fairly balanced, this amounts to space for a tree containing elements. In the worst case, when the tree takes the form of a chain, the height of the tree is so the algorithm takes space. In 1968, Donald Knuth asked whether a non-recursive algorithm for in-order traversal exists, that uses no stack and leaves the tree unmodified. One of the solutions to this problem is tree threading, presented by J. M. Morris in 1979. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Threaded binary tree」の詳細全文を読む スポンサード リンク
|